﻿https://leetcode.cn/problems/substring-with-concatenation-of-all-words/
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        if (words.empty() || s.empty())
            return ret;
        unordered_map<string, int> hash2;
        int len = words[0].length();
        int m = words.size();
        int left = 0;
        int n = len * m;
        for (auto& str : words)
            hash2[str]++;
        for (int i = 0; i < len; i++) {
            unordered_map<string, int> hash1;
            for (int right = i, left = i, count = 0; right + len <= s.size();right += len) {
                string in = s.substr(right, len);
                // 进窗⼝ + 维护 count
                if (++hash1[in] <= hash2[in])
                    count++;
                if (right - left + 1 > n) // 判断
                {
                    string out = s.substr(left, len);
                    // 出窗⼝ + 维护 count
                    if (--hash1[out] < hash2[out])
                        count--;
                    left += len;
                }
                if (count == m)
                    ret.push_back(left);
            }
        }
        return ret;
    }
};